﻿#include <iostream>

static bool canNeighborMultipleOf4(const int* numbers, const size_t count)
{
    // 奇数的个数
    int oddNumberCount = 0;
    // 能被4整除的偶数
    int evenNumberCountMultipleOf4 = 0;
    // 不能被4整除的偶数
    int evenNumberCountNotMultipleOf4 = 0;
    int cur;
    for (int i = 0; i < count; i++)
    {
        cur = numbers[i];
        if (cur % 2 == 1)
        {
            ++oddNumberCount;
        }
        else if (cur % 4 == 0)
        {
            ++evenNumberCountMultipleOf4;
        }
        else
        {
            ++evenNumberCountNotMultipleOf4;
        }
    }

    if (oddNumberCount == count) return false;
    if (evenNumberCountMultipleOf4 == count) return true;
    if (evenNumberCountNotMultipleOf4 == count && (evenNumberCountNotMultipleOf4 % 2 == 0)) return true;

    if (evenNumberCountNotMultipleOf4 == 0)
    {
        if (oddNumberCount == 1)
        {
            return evenNumberCountMultipleOf4 >= 1;
        }

        if (oddNumberCount > 1)
        {
            return evenNumberCountMultipleOf4 >= oddNumberCount - 1;
        }
    }

    if (evenNumberCountNotMultipleOf4 > 0)
    {
        return evenNumberCountMultipleOf4 >= oddNumberCount;
    }

    return false;
}


/**
 * 给定一个数组arr，如果通过调整可以做到arr中任意两个相邻的数字相乘是4的倍数，返回true；如果不能返回false。
 *
 * 思路: 将数字分为三类：
 * a. 奇数
 * b. 能被2整除但是不能被4整除的数字
 * c. 能被4整除的数字
 *
 * 情况1: b==0, 这种情况下，只要保证数字排列是 acacac...
 * 这种情况下，
 * if (count(a) == 1) {
 *     count(c) >= 1
 * }
 *
 * if (count(a) > 1) {
 *     count(c) >= count(a)-1
 * }
 *
 * 情况2: b>0, 这种情况下，将b排在最前, 然后接c，然后接acacac... 即 bbb...cacaca...
 * 基于情况1，c需要再追加一个
 */
int main_TwoNumbersNextToEachOtherIsMultipleOfFour()
{
    int numbers[] = { 3,2,2,2,3,4 };
    int count = sizeof(numbers) / sizeof(int);
    bool can = canNeighborMultipleOf4(numbers, count);
    printf("%d", can);
    return 0;
}